W1. Таблицы истинности, нормальные формы (DNF, CNF)

Автор

Zakhar Podyakov

Дата публикации

17 сентября 2025 г.

Quiz | Flashcards

1. Кратко

1.1 Высказывания (propositions) и логические значения

В логике высказывание (proposition) — это утверждение, которое можно однозначно считать истинным (True) или ложным (False), но не обоими сразу. Это базовый кирпичик логических выражений. Например, «небо голубое» — высказывание. «Который час?» — нет, потому что это вопрос и ему нельзя приписать истинностное значение. В дискретной математике и в вычислениях эти значения кодируют числами:

  • Истина (True) кодируется как 1.
  • Ложь (False) кодируется как 0.
1.2 Логические операторы (logical operators)

Логические операторы — символы, соединяющие высказывания в более сложные формулы. У каждого оператора есть правило, как по значениям операндов получить значение всей формулы.

1.2.1 Отрицание (NOT)

Оператор отрицания (Negation), обозначаемый \(¬\) (например, \(¬P\)), меняет истинностное значение высказывания на противоположное. Если \(P\) истинно, \(¬P\) ложно; если \(P\) ложно, \(¬P\) истинно. Соответствует слову «не».

1.2.2 Конъюнкция (AND)

Оператор конъюнкции (Conjunction), обозначаемый \(&\) или \(∧\) (например, \(P ∧ Q\)), соединяет два высказывания. Результат истинен только если оба операнда истинны. Если хотя бы один ложен, результат ложен. Соответствует союзу «и».

1.2.3 Дизъюнкция (OR)

Оператор дизъюнкции (Disjunction), обозначаемый \(∨\) (например, \(P ∨ Q\)), даёт истину, если хотя бы одно из высказываний истинно. Ложен только когда оба ложны. Это включающее ИЛИ (inclusive OR).

1.2.4 Импликация (IF…THEN)

Оператор импликации (Implication), обозначаемый \(→\) (например, \(P → Q\)), задаёт условное утверждение: «если \(P\), то \(Q\)». Выражение \(P → Q\) ложно только когда \(P\) истинно, а \(Q\) ложно; во всех остальных случаях оно истинно. Это может казаться непривычным: удобная аналогия — «обещание»: «если я сдам экзамен (\(P\)), то отмечу это (\(Q\))». Обещание нарушается только если экзамен сдан, а празднования не было; если экзамен не сдан, обещание нельзя считать нарушенным независимо от того, празднуете вы или нет.

1.2.5 Эквиваленция (IF AND ONLY IF)

Оператор эквиваленции (Equivalence), обозначаемый \(↔\) (например, \(P ↔ Q\)), в англоязычных текстах называют biconditional (двусторонняя импликация). Результат истинен только когда оба высказывания имеют одинаковое истинностное значение (оба истинны или оба ложны).

1.3 Таблицы истинности (truth tables)

Таблица истинности (truth table) — инструмент, который для каждого набора значений пропозициональных переменных систематически даёт значение сложной формулы.

  • Построение (construction): для формулы с \(n\) различными переменными нужно \(2^n\) строк, чтобы перечислить все наборы значений.
  • Структура (structure): первые столбцы — все комбинации значений переменных; далее столбцы для подформул, пока в последнем столбце не окажется итоговый результат.
1.4 Нормальные формы (normal forms)

Нормальная форма (normal form) — стандартизированный вид записи логической формулы. Она полезна для сравнения и упрощения формул и для автоматической обработки в информатике. Чаще всего используют дизъюнктивную нормальную форму (DNF, Disjunctive Normal Form) и конъюнктивную нормальную форму (CNF, Conjunctive Normal Form).

1.4.1 Дизъюнктивная нормальная форма (DNF)

Формула находится в DNF, если это дизъюнкция (цепочка ИЛИ) конъюнктов (цепочек И из литералов). Литерал (literal) — переменная или её отрицание.

  • Структура: \((A \land \neg B) \lor (C \land D) \lor (\neg E)\)
  • Смысл: DNF перечисляет конкретные сценарии, при которых формула истинна. Каждый конъюнкт — один такой сценарий; вся формула истинна, если истинен хотя бы один из них.
Алгоритм получения DNF по таблице истинности
  1. Выберите все строки, где итоговый столбец равен 1 (True).
  2. Для каждой такой строки составьте конъюнкт (И-выражение).
  3. Если в строке переменная равна 1, запишите её как есть (например, \(A\)).
  4. Если переменная равна 0, запишите отрицание (например, \(¬A\)).
  5. Соедините все конъюнкты оператором дизъюнкции (\(∨\)).
1.4.2 Конъюнктивная нормальная форма (CNF)

Формула находится в CNF, если это конъюнкция (цепочка И) дизъюнктов (цепочек ИЛИ из литералов).

  • Структура: \((A \lor \neg B) \land (C \lor D) \land (\neg E)\)
  • Смысл: CNF задаёт набор ограничений: все они должны выполняться одновременно. Достаточно одной ложной скобки, чтобы вся формула стала ложной.
Алгоритм получения CNF по таблице истинности
  1. Выберите все строки, где итог равен 0 (False).
  2. Для каждой такой строки составьте дизъюнкт (ИЛИ-выражение).
  3. Если в строке переменная равна 0, запишите её как есть (например, \(A\)).
  4. Если переменная равна 1, запишите отрицание (например, \(¬A\)). (Это противоположно правилу для DNF.)
  5. Соедините все дизъюнкты оператором конъюнкции (\(∧\)).

2. Определения

  • Высказывание (proposition): повествовательное предложение, однозначно истинное или ложное.
  • Таблица истинности (truth table): таблица значений формулы для всех наборов значений переменных.
  • Литерал (literal): пропозициональная переменная (например, \(A\)) или её отрицание (например, \(¬A\)).
  • Конъюнкт (minterm): конъюнкция одного или нескольких литералов, например \(A ∧ ¬B ∧ C\).
  • Дизъюнкт (maxterm): дизъюнкция одного или нескольких литералов, например \(A ∨ ¬B ∨ C\).
  • DNF (Disjunctive Normal Form): формула как дизъюнкция конъюнктов; «ИЛИ из И».
  • CNF (Conjunctive Normal Form): формула как конъюнкция дизъюнктов; «И из ИЛИ».

3. Формулы

  • Эквивалентность импликации (implication equivalence): \(P → Q \equiv ¬P ∨ Q\)
  • Эквивалентность эквиваленции (biconditional equivalence): \(P ↔ Q \equiv (P → Q) ∧ (Q → P) \equiv (¬P ∨ Q) ∧ (P ∨ ¬Q)\)
  • Общая формула для DNF: \[f = \bigvee_{f(\sigma_1, ..., \sigma_n)=1} (x_1^{\sigma_1} \land ... \land x_n^{\sigma_n})\]
  • Общая формула для CNF: \[f = \bigwedge_{f(\sigma_1, ..., \sigma_n)=0} (x_1^{\overline{\sigma_1}} \lor ... \lor x_n^{\overline{\sigma_n}})\]

4. Примеры

4.1. Построить таблицу истинности (Лаба 1, Задание 1)

Постройте полную таблицу истинности для выражения \(¬a ∨ b\).

Показать решение
  1. Столбцы: нужны \(a\), \(b\), \(¬a\) и итог \(¬a ∨ b\).
  2. Строки входов: для двух переменных \(2^2=4\) набора.
  3. Столбец \(¬a\): противоположен столбцу \(a\).
  4. Столбец \(¬a ∨ b\): истина, если истинно \(¬a\) или \(b\).
a b ¬a ¬a ∨ b
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
Ответ: последовательность значений формулы — (1, 1, 0, 1).
4.2. Получить DNF по таблице истинности (Лаба 1, Задание 1)

Получите DNF по таблице истинности, заданной вектором \(T(a, b) = (0110)\).

Показать решение
  1. Таблица: вектор \(T(a,b)=(0110)\) задаёт столбец значений \(f\) при переборе \((a,b)\) в порядке \((0,0),(0,1),(1,0),(1,1)\).
a b f(a,b)
0 0 0
0 1 1
1 0 1
1 1 0
  1. Строки с 1: функция равна 1 на наборах \((0,1)\) и \((1,0)\).
  2. Минтермы (minterms): для каждой такой строки — конъюнкт: 0 → отрицание, 1 → переменная как есть.
    • Строка 2 (\(a=0\), \(b=1\)): \(¬a ∧ b\)
    • Строка 3 (\(a=1\), \(b=0\)): \(a ∧ ¬b\)
  3. DNF: дизъюнкция минтермов.
Ответ: \((¬a ∧ b) ∨ (a ∧ ¬b)\).
4.3. Получить CNF по таблице истинности (Лаба 1, Задание 2)

Получите CNF по таблице истинности, заданной вектором \(T(a, b) = (1000)\).

Показать решение
  1. Таблица: вектор \((1000)\) задаёт столбец \(f\).
a b f(a,b)
0 0 1
0 1 0
1 0 0
1 1 0
  1. Строки с 0: наборы \((0,1)\), \((1,0)\), \((1,1)\).
  2. Макстермы (maxterms): для строки с 0 — дизъюнкт: 0 → переменная как есть, 1 → отрицание.
    • Строка 2 (\(a=0\), \(b=1\)): \(a ∨ ¬b\)
    • Строка 3 (\(a=1\), \(b=0\)): \(¬a ∨ b\)
    • Строка 4 (\(a=1\), \(b=1\)): \(¬a ∨ ¬b\)
  3. CNF: конъюнкция макстермов.
Ответ: \((a ∨ ¬b) ∧ (¬a ∨ b) ∧ (¬a ∨ ¬b)\).
4.4. Получить DNF и CNF по таблице истинности (Лаба 1, Задание a)

Найдите и DNF, и CNF для таблицы \(T(x, y) = (1001)\).

Показать решение
  1. Таблица:
x y f(x,y)
0 0 1
0 1 0
1 0 0
1 1 1
  1. DNF:
    • Строки с 1: \((0,0)\) и \((1,1)\).
    • Минтермы: \((¬x ∧ ¬y)\) и \((x ∧ y)\).
    • Дизъюнкция: \((¬x ∧ ¬y) ∨ (x ∧ y)\).
  2. CNF:
    • Строки с 0: \((0,1)\) и \((1,0)\).
    • Макстермы: \((x ∨ ¬y)\) и \((¬x ∨ y)\).
    • Конъюнкция: \((x ∨ ¬y) ∧ (¬x ∨ y)\).

Ответ:

  • DNF: \((¬x ∧ ¬y) ∨ (x ∧ y)\)
  • CNF: \((x ∨ ¬y) ∧ (¬x ∨ y)\)
4.5. Получить DNF и CNF по таблице истинности (Лаба 1, Задание b)

Найдите DNF и CNF для \(T(x_1, x_2) = (0100)\).

Показать решение
  1. Таблица:
x₁ x₂ f(x₁,x₂)
0 0 0
0 1 1
1 0 0
1 1 0
  1. DNF:
    • Строка с 1: только \((0,1)\).
    • Минтерм: \(¬x_1 ∧ x_2\).
    • DNF — один минтерм.
  2. CNF:
    • Строки с 0: \((0,0)\), \((1,0)\), \((1,1)\).
    • Макстермы: \((x_1 ∨ x_2)\), \((¬x_1 ∨ x_2)\), \((¬x_1 ∨ ¬x_2)\).
    • Конъюнкция: \((x_1 ∨ x_2) ∧ (¬x_1 ∨ x_2) ∧ (¬x_1 ∨ ¬x_2)\).

Ответ:

  • DNF: \(¬x_1 ∧ x_2\)
  • CNF: \((x_1 ∨ x_2) ∧ (¬x_1 ∨ x_2) ∧ (¬x_1 ∨ ¬x_2)\)
4.6. Получить DNF и CNF по таблице истинности (Лаба 1, Задание c)

Найдите DNF и CNF для \(T(a, b, c) = (01010110)\).

Показать решение
  1. Таблица:
a b c f(a,b,c)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
  1. DNF:
    • Строки с 1: \((0,0,1)\), \((0,1,1)\), \((1,0,1)\), \((1,1,0)\).
    • Минтермы: \((¬a ∧ ¬b ∧ c)\), \((¬a ∧ b ∧ c)\), \((a ∧ ¬b ∧ c)\), \((a ∧ b ∧ ¬c)\).
    • Дизъюнкция: \((¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)\).
  2. CNF:
    • Строки с 0: \((0,0,0)\), \((0,1,0)\), \((1,0,0)\), \((1,1,1)\).
    • Макстермы: \((a ∨ b ∨ c)\), \((a ∨ ¬b ∨ c)\), \((¬a ∨ b ∨ c)\), \((¬a ∨ ¬b ∨ ¬c)\).
    • Конъюнкция: \((a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c)\).

Ответ:

  • DNF: \((¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)\)
  • CNF: \((a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c)\)
4.7. Получить DNF и CNF по таблице истинности (Лаба 1, Задание d)

Найдите DNF и CNF для \(T(y_1, y_2, y_3) = (10000111)\).

Показать решение
  1. Таблица:
y₁ y₂ y₃ f(y₁,y₂,y₃)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
  1. DNF:
    • Строки с 1: \((0,0,0)\), \((1,0,1)\), \((1,1,0)\), \((1,1,1)\).
    • Минтермы: \((¬y_1 ∧ ¬y_2 ∧ ¬y_3)\), \((y_1 ∧ ¬y_2 ∧ y_3)\), \((y_1 ∧ y_2 ∧ ¬y_3)\), \((y_1 ∧ y_2 ∧ y_3)\).
    • Дизъюнкция: \((¬y_1 ∧ ¬y_2 ∧ ¬y_3) ∨ (y_1 ∧ ¬y_2 ∧ y_3) ∨ (y_1 ∧ y_2 ∧ ¬y_3) ∨ (y_1 ∧ y_2 ∧ y_3)\).
  2. CNF:
    • Строки с 0: \((0,0,1)\), \((0,1,0)\), \((0,1,1)\), \((1,0,0)\).
    • Макстермы: \((y_1 ∨ y_2 ∨ ¬y_3)\), \((y_1 ∨ ¬y_2 ∨ y_3)\), \((y_1 ∨ ¬y_2 ∨ ¬y_3)\), \((¬y_1 ∨ y_2 ∨ y_3)\).
    • Конъюнкция: \((y_1 ∨ y_2 ∨ ¬y_3) ∧ (y_1 ∨ ¬y_2 ∨ y_3) ∧ (y_1 ∨ ¬y_2 ∨ ¬y_3) ∧ (¬y_1 ∨ y_2 ∨ y_3)\).

Ответ:

  • DNF: \((¬y_1 ∧ ¬y_2 ∧ ¬y_3) ∨ (y_1 ∧ ¬y_2 ∧ y_3) ∨ (y_1 ∧ y_2 ∧ ¬y_3) ∨ (y_1 ∧ y_2 ∧ y_3)\)
  • CNF: \((y_1 ∨ y_2 ∨ ¬y_3) ∧ (y_1 ∨ ¬y_2 ∨ y_3) ∧ (y_1 ∨ ¬y_2 ∨ ¬y_3) ∧ (¬y_1 ∨ y_2 ∨ y_3)\)
4.8. Построить таблицу истинности (Лаба 1, Задание a)

Постройте полную таблицу истинности для \((p ∧ q) ∨ ¬q\).

Показать решение
  1. Столбцы: \(p\), \(q\), промежуточно \(p ∧ q\) и \(¬q\), затем итог.
  2. Наборы: четыре строки.
  3. \(p ∧ q\): 1 только при \(p=q=1\).
  4. \(¬q\): противоположно \(q\).
  5. \((p ∧ q) ∨ ¬q\): 1, если истинно \((p ∧ q)\) или \(¬q\).
p q p ∧ q ¬q (p ∧ q) ∨ ¬q
0 0 0 1 1
0 1 0 0 0
1 0 1 1 1
1 1 1 0 1
Ответ: последовательность значений — (1, 0, 1, 1).
4.9. Построить таблицу истинности (Лаба 1, Задание b)

Постройте полную таблицу истинности для \((A ∧ B) → C\).

Показать решение
  1. Столбцы: \(A,B,C\), затем \(A ∧ B\), затем импликация.
  2. Наборы: \(2^3=8\) строк.
  3. \(A ∧ B\): 1 только при \(A=B=1\).
  4. Импликация: ложна только при истинной левой части и ложной правой.
A B C A ∧ B (A ∧ B) → C
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
Ответ: (1, 1, 1, 1, 1, 1, 0, 1).
4.10. Построить таблицу истинности (Лаба 1, Задание c)

Постройте полную таблицу истинности для \((x ∨ ¬y) → ¬z\).

Показать решение
  1. Столбцы: \(x,y,z\), затем \(¬y\), \(¬z\), \((x ∨ ¬y)\), импликация к \(¬z\).
  2. Наборы: 8 строк.
  3. Отрицания: заполнить \(¬y\), \(¬z\).
  4. \(x ∨ ¬y\): 1, если \(x=1\) или \(¬y=1\).
  5. Импликация: ложна только при истинном \((x ∨ ¬y)\) и ложном \(¬z\).
x y z ¬y ¬z x ∨ ¬y (x ∨ ¬y) → ¬z
0 0 0 1 1 1 1
0 0 1 1 0 1 0
0 1 0 0 1 0 1
0 1 1 0 0 0 1
1 0 0 1 1 1 1
1 0 1 1 0 1 0
1 1 0 0 1 1 1
1 1 1 0 0 1 0
Ответ: (1, 0, 1, 1, 1, 0, 1, 0).
4.11. Построить таблицу истинности (Лаба 1, Задание d)

Постройте полную таблицу истинности для \((φ ↔ ψ) → ¬(ψ → γ)\).

Показать решение
  1. Столбцы: \(φ, ψ, γ\), промежуточно \(φ ↔ ψ\), \(ψ → γ\), \(¬(ψ → γ)\), затем итог.
  2. Наборы: 8 строк.
  3. \(φ ↔ ψ\): 1, когда \(φ\) и \(ψ\) совпадают.
  4. \(ψ → γ\): ложно только при \(ψ=1\), \(γ=0\).
  5. \(¬(ψ → γ)\): отрицание предыдущего столбца.
  6. Итоговая импликация: ложна только при истинном \((φ ↔ ψ)\) и ложном \(¬(ψ → γ)\).
φ ψ γ φ ↔︎ ψ ψ → γ ¬(ψ → γ) (φ ↔︎ ψ) → ¬(ψ → γ)
0 0 0 1 1 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 1
0 1 1 0 1 0 1
1 0 0 0 1 0 1
1 0 1 0 1 0 1
1 1 0 1 0 1 1
1 1 1 1 1 0 0
Ответ: (0, 0, 1, 1, 1, 1, 1, 0).
4.12. Построить таблицу истинности (Лаба 1, Задание e)

Постройте полную таблицу истинности для \((x_1 ∧ (x_2 → y)) → (x_1 ∨ ¬y)\).

Показать решение
  1. Столбцы: \(x_1, x_2, y\), затем \(x_2 → y\), \(x_1 ∧ (x_2 → y)\), \(¬y\), \(x_1 ∨ ¬y\), итог.
  2. Наборы: 8 строк.
  3. \(x_2 → y\): ложно только при \(x_2=1\), \(y=0\).
  4. Левая часть \(x_1 ∧ (x_2 → y)\): 1 только при \(x_1=1\) и истинном \((x_2 → y)\).
  5. \(¬y\): противоположно \(y\).
  6. Правая часть \(x_1 ∨ ¬y\): 1, если \(x_1=1\) или \(¬y=1\).
  7. Итоговая импликация: ложна только при истинной левой и ложной правой части.
x₁ x₂ y x₂ → y x₁ ∧ (x₂ → y) ¬y x₁ ∨ ¬y (x₁ ∧ (x₂ → y)) → (x₁ ∨ ¬y)
0 0 0 1 0 1 1 1
0 0 1 1 0 0 0 1
0 1 0 0 0 1 1 1
0 1 1 1 0 0 0 1
1 0 0 1 1 1 1 1
1 0 1 1 1 0 1 1
1 1 0 0 0 1 1 1
1 1 1 1 1 0 1 1
Ответ: (1, 1, 1, 1, 1, 1, 1, 1). Формула — тавтология (tautology).
4.13. Построить таблицу истинности (Туториал 1, Задание 1)

Постройте полную таблицу истинности для \(¬a ∨ b\).

Показать решение
  1. Столбцы: \(a\), \(b\), \(¬a\), \(¬a ∨ b\).
  2. Наборы: \(2^2=4\) строки.
  3. \(¬a\): противоположно \(a\).
  4. \(¬a ∨ b\): дизъюнкция истинна, если истинно \(¬a\) или \(b\).
a b ¬a ¬a ∨ b
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
Ответ: (1, 1, 0, 1).
4.14. Построить таблицу истинности (Туториал 1, Задание 2)

Постройте полную таблицу истинности для \((¬a ∨ b) → b\).

Показать решение
  1. Столбцы: \(a\), \(b\), \(¬a\), \(¬a ∨ b\), \((¬a ∨ b) → b\).
  2. Наборы: четыре строки.
  3. \(¬a\): противоположно \(a\).
  4. \(¬a ∨ b\): 1, если \(¬a\) или \(b\).
  5. Импликация: \(X → Y\) ложна только при \(X=1\), \(Y=0\).
a b ¬a ¬a ∨ b (¬a ∨ b) → b
0 0 1 1 0
0 1 1 1 1
1 0 0 0 1
1 1 0 1 1
Ответ: (0, 1, 1, 1).
4.15. Получить DNF по таблице истинности (Туториал 1, Задание 1)

Получите DNF по вектору \(T(a, b) = (1110)\).

Показать решение
  1. Таблица: вектор \((1110)\) задаёт столбец \(f\).
a b f(a,b)
0 0 1
0 1 1
1 0 1
1 1 0
  1. Строки с 1: \((0,0)\), \((0,1)\), \((1,0)\).
  2. Минтермы: 0 → отрицание, 1 → как есть.
    • Строка 1 (\(a=0\), \(b=0\)): \(¬a ∧ ¬b\)
    • Строка 2 (\(a=0\), \(b=1\)): \(¬a ∧ b\)
    • Строка 3 (\(a=1\), \(b=0\)): \(a ∧ ¬b\)
  3. Дизъюнкция минтермов.
Ответ: \((¬a ∧ ¬b) ∨ (¬a ∧ b) ∨ (a ∧ ¬b)\).
4.16. Получить CNF по таблице истинности (Туториал 1, Задание 2)

Получите CNF по вектору \(T(a, b) = (1000)\).

Показать решение
  1. Таблица: вектор \((1000)\).
a b f(a,b)
0 0 1
0 1 0
1 0 0
1 1 0
  1. Строки с 0: \((0,1)\), \((1,0)\), \((1,1)\).
  2. Макстермы: 0 → переменная как есть, 1 → отрицание.
    • Строка 2: \(a ∨ ¬b\)
    • Строка 3: \(¬a ∨ b\)
    • Строка 4: \(¬a ∨ ¬b\)
  3. Конъюнкция макстермов.
Ответ: \((a ∨ ¬b) ∧ (¬a ∨ b) ∧ (¬a ∨ ¬b)\).
4.17. Построить таблицу истинности (Туториал 1, Задание 3)

Постройте полную таблицу истинности для \((¬a → b) ↔ (¬b ∧ c)\).

Показать решение
  1. Столбцы: \(a,b,c\), затем \(¬a\), \(¬b\), \((¬a → b)\), \((¬b ∧ c)\), итог.
  2. Наборы: \(2^3=8\) строк.
  3. Отрицания: \(¬a\), \(¬b\).
  4. Левая часть \((¬a → b)\): ложна только при \(¬a=1\), \(b=0\).
  5. Правая часть \((¬b ∧ c)\): 1 только при \(¬b=1\) и \(c=1\).
  6. Эквиваленция: 1, когда обе части совпадают по значению.
a b c ¬a ¬b ¬a → b ¬b ∧ c (¬a → b) ↔︎ (¬b ∧ c)
0 0 0 1 1 0 0 1
0 0 1 1 1 0 1 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 1 0 1 1 1 1
1 1 0 0 0 1 0 0
1 1 1 0 0 1 0 0
Ответ: (1, 0, 0, 0, 0, 1, 0, 0).